package DP;

/**
 * 公共最长子序列
 * https://leetcode-cn.com/problems/longest-common-subsequence/
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484486&idx=1&sn=0bdcb94c6390307ea32427757ec0072c&chksm=9bd7fa4eaca073583623cdb93b05dc9e1d0757b25697bb40b29b3e450124e929ff1a8eaac50f&mpshare=1&scene=1&srcid=&sharer_sharetime=1581753712169&sharer_shareid=6c224d4e946f3800a20244497b984d86#rd
 */
public class LCS {

    /**
     * 这个dp的含义是，dp[i][j] 对于s1[1..i]和s2[1..j]，它们的 LCS 长度是dp[i][j]。
     */
    public int longestCommonSubsequence(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();

        int n = s1.length;
        int m = s2.length;

        if(n == 0 || m== 0) return 0;
        int[][] dp = new int[n+1][m+1];

        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m;j++){
                //字符串相等，就直接+1，不用比较取最大
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1);//为什么是 i-1 j-1 很关键，因为这两个字符都不能再用了，要取上一段的！！！
                    //这里加Math.max是因为， i j 有可能
                }else{//如果字符串不相等，那就要取上面最大，还是下面最大，给记录下去。
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[n][m];
    }

    //打印出来,通过使用  一个二维的数组记录下来
    public int longestCommonSubsequence_print(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int n = s1.length;
        int m = s2.length;
        if(n == 0 || m== 0) return 0;
        int[][] dp = new int[n+1][m+1];
        int[][] router = new int[n+1][m+1];

        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m;j++){
                //字符串相等，就直接+1，不用比较取最大
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;//为什么是 i-1 j-1 很关键，因为这两个字符都不能再用了，要取上一段的！！！
                    router[i][j] = 2;
                }else{//如果字符串不相等，那就要取上面最大，还是下面最大，给记录下去。
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    if(dp[i][j] == dp[i-1][j]) router[i][j]=0;
                    else router[i][j] = 1;
                }
            }
        }

        char[] res = new char[dp[n][m]];
        int i=n,j=m,p=dp[n][m]-1;
        while (i>0 && j>0){
            if(router[i][j] == 0){
                i--;
            }else if(router[i][j]==1){
                j--;
            }else{
                res[p] = s1[i-1];
                p--;i--;j--;
            }
        }
        System.out.println(res);

        return dp[n][m];
    }

    /**
     * 1.dp方程： dp[i][j]=dp[i-1][j-1]+1; //text1[i-1]==text2[j-1]
     * dp[i][j]=max(dp[i][j],dp[i][j-1]); //text1[i-1]!=text2[j-1]
     * 2.在利用二维dp数组存储结果时，需要用到dp[i-1][j-1] (左上方),dp[i-1][j] (上边),dp[i][j-1] (左边)。
     * 3.优化为滚动数组存储结果时，由于在从左到右计算dp[j] (dp[i][j]) 的时候dp[j-1] (dp[i-1][j-1]) 已被更新为dp[j-1]（dp[i][j-1]），所以只需要提前定义一个变量last去存储二维dp数组左上方的值dp[i-1][j-1],即未被更新前的dp[j-1];
     * 注意：计算每一行的第一个元素时候，last需要初始化为0。
     */
    public int longestCommonSubsequence2(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();

        int n = s1.length;
        int m = s2.length;
        int last = 0;
        int temp = 0;

        if(n == 0 || m== 0) return 0;
        int[] dp = new int[m+1];

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m;j++){
                temp = dp[j];//开始新一轮的计算，要存储目前算到的最大的 dj[j],其实也就是二维DP数组的最右下角
                //字符串相等，就直接+1，不用比较取最大
                if(s1[i-1] == s2[j-1]){
                    dp[j] = last +1;//last 其实记录的是左上角的
                }else{//如果字符串不相等，那就要取上面最大，还是下面最大，给记录下去。
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
                last=temp;
            }
        }

        return dp[m];
    }

    public static void main(String[] args){
        LCS l = new LCS();
        l.longestCommonSubsequence_print("abad", "acd");

    }


}
